#ifndef SGU_TEMPLCOLL_H
#define SGU_TEMPLCOLL_H

SGU_NS_BEGIN

template <class T> void set_difference(const std::set<T> & a, const std::set<T> & b, std::set<T> & c)
{
	ASSERT(c.empty());
	std::vector<T> va(a.size());
	std::vector<T> vb(b.size());
	std::vector<T> vc(Max(a.size(),b.size()));

	typename std::set<T>::const_iterator cits;
	typename std::vector<T>::iterator itv;

	for(cits=a.begin(), itv=va.begin() ; cits!=a.end() && itv!=va.end() ; ++cits, ++itv) *itv = *cits;
	for(cits=b.begin(), itv=vb.begin() ; cits!=b.end() && itv!=vb.end() ; ++cits, ++itv) *itv = *cits;

	itv = set_difference(va.begin(),va.end(),vb.begin(),vb.end(),vc.begin());
	vc.resize(itv - vc.begin());

	typename std::vector<T>::const_iterator citv;
	ITERATEX(citv,vc) c.insert(*citv);
}

template <class T> void set_union(const std::set<T> & a, const std::set<T> & b, std::set<T> & c)
{
	ASSERT(c.empty());
	std::vector<T> va(a.size());
	std::vector<T> vb(b.size());
	std::vector<T> vc(a.size() + b.size());

	typename std::set<T>::const_iterator cits;
	typename std::vector<T>::iterator itv;

	for(cits=a.begin(), itv=va.begin() ; cits!=a.end() && itv!=va.end() ; ++cits, ++itv) *itv = *cits;
	for(cits=b.begin(), itv=vb.begin() ; cits!=b.end() && itv!=vb.end() ; ++cits, ++itv) *itv = *cits;

	itv = set_union(va.begin(),va.end(),vb.begin(),vb.end(),vc.begin());
	vc.resize(itv - vc.begin());

	typename std::vector<T>::const_iterator citv;
	ITERATEX(citv,vc) c.insert(*citv);
}

template <class T> void set_intersection(const std::set<T> & a, const std::set<T> & b, std::set<T> & c)
{
	ASSERT(c.empty());
	std::vector<T> va(a.size());
	std::vector<T> vb(b.size());
	std::vector<T> vc(MIN(a.size(),b.size()));

	typename std::set<T>::const_iterator cits;
	typename std::vector<T>::iterator itv;

	for(cits=a.begin(), itv=va.begin() ; cits!=a.end() && itv!=va.end() ; ++cits, ++itv) *itv = *cits;
	for(cits=b.begin(), itv=vb.begin() ; cits!=b.end() && itv!=vb.end() ; ++cits, ++itv) *itv = *cits;

	itv = set_intersection(va.begin(),va.end(),vb.begin(),vb.end(),vc.begin());
	vc.resize(itv - vc.begin());

	typename std::vector<T>::const_iterator citv;
	ITERATEX(citv,vc) c.insert(*citv);
}


//*******************************************************

template <class X, class Y> BOStorage & operator << (BOStorage & s, const std::pair<X,Y> & a)
{
	return s << a.first << a.second;
}

template <class X, class Y> BIStorage & operator >> (BIStorage & s, std::pair<X,Y> & a)
{
	return s >> a.first >> a.second;
}

template <class X, class Y> TOStorage & operator << (TOStorage & s, const std::pair<X,Y> & a)
{
	return s << "(" << a.first << "," << a.second << ")";
}

template <class X, class Y> TIStorage & operator >> (TIStorage & s, std::pair<X,Y> & a)
{
	return s >> "(" >> a.first >> "," >> a.second >> ")";
}




//*****************************************************



template<class X, class Y> class BiUnivoc
{
	public:
	BiUnivoc()
	{
	}

	virtual ~BiUnivoc()
	{
	}

	bool insert(const X & x, const Y & y)
	{
		std::pair<typename std::map<Y,X>::iterator,bool> k1 = _mapXY.insert(make_pair(x,y));
		std::pair<typename std::map<Y,X>::iterator,bool> k2 = _mapYX.insert(make_pair(y,x));

		bool retval = k1.second && k2.second;
		if(!retval)
		{
			if(k1.second) _mapXY.erase(k1.first);
			if(k2.second) _mapYX.erase(k2.first);
		};

		return retval;
	}

	bool eraseX(const X & x)
	{
		typename std::map<X,Y>::iterator i1 = _mapXY.find(x);
		if(i1==_mapXY.end()) return false;
		typename std::map<Y,X>::iterator i2 = _mapYX.find(i1->second);
		ASSERT(i2!=_mapYX.end());
		_mapXY.erase(i1);
		_mapYX.erase(i2);
		return true;
	}

	bool eraseY(const Y & y)
	{
		typename std::map<Y,X>::iterator i1 = _mapYX.find(y);
		if(i1==_mapYX.end()) return false;
		typename std::map<X,Y>::iterator i2 = _mapXY.find(i1->second);
		ASSERT(i2!=_mapXY.end());
		_mapYX.erase(i1);
		_mapXY.erase(i2);
		return true;
	}

	bool findX(const X & x, Y & y) const
	{
		typename std::map<X,Y>::const_iterator i = _mapXY.find(x);
		if(i==_mapXY.end()) return false;
		y = i->second;
		return true;
	}

	bool findY(const Y & y, X & x) const
	{
		typename std::map<Y,X>::const_iterator i = _mapYX.find(y);
		if(i==_mapYX.end()) return false;
		x = i->second;
		return true;
	}

	bool IsX(const X & x) const
	{
		typename std::map<X,Y>::const_iterator i = _mapXY.find(x);
		if(i==_mapXY.end()) return false;
		return true;
	}

	bool isY(const Y & y) const
	{
		typename std::map<Y,X>::const_iterator i = _mapYX.find(y);
		if(i==_mapYX.end()) return false;
		return true;
	}


	const X & firstX() const
	{
		typename std::map<X,Y>::const_iterator i = _mapXY.begin();
		ASSERT(i!=_mapXY.end());
		return i->first;
	}

	const Y & firstY() const
	{
		typename std::map<Y,X>::const_iterator i = _mapYX.begin();
		ASSERT(i!=_mapYX.end());
		return i->first;
	}

	const X & lastX() const
	{
		typename std::map<X,Y>::const_reverse_iterator i = _mapXY.rbegin();
		ASSERT(i!=_mapXY.rend());
		return i->first;
	}

	const Y & lastY() const
	{
		typename std::map<Y,X>::const_reverse_iterator i = _mapYX.rbegin();
		ASSERT(i!=_mapYX.rend());
		return i->first;
	}

	bool isEmpty() const
	{
		bool b1 = _mapXY.empty();
		bool b2 = _mapYX.empty();
		ASSERT(b1==b2);
		return (b1&&b2);
	}


	private:
	std::map<X,Y> _mapXY;
	std::map<Y,X> _mapYX;

};




//**************************************************************


template <class T> BOStorage & operator <<(BOStorage & s, const std::vector<T> & a)
{
	s<<a.size();
	typename std::vector<T>::const_iterator i;
	ITERATEX(i,a) s<<*i;
	return s;
}

template <class T> TOStorage & operator <<(TOStorage & s, const std::vector<T> & a)
{
	s << "@[" << a.size() << "]" << s.BEGIN;
	typename std::vector<T>::const_iterator it;
	ITERATEX(it,a) s << s.NL << *it << ";";
	s << s.END;
	return s;
}



template <class T> BIStorage & operator >>(BIStorage & s, std::vector<T> & a)
{
	size_t z;
	s>>z;
	a.resize(z);
	typename std::vector<T>::iterator i;
	ITERATEX(i,a) s>>*i;
	return s;
}

template <class T> TIStorage & operator >>(TIStorage & s, std::vector<T> & a)
{
	size_t z;
	s >> "@ [" >> z >> "]" >> s.BEGIN;
	a.resize(z);
	typename std::vector<T>::iterator it;
	ITERATEX(it,a) s >> *it >> ";";
	s >> s.END;
	return s;
}


template <class T> BOStorage & operator <<(BOStorage & s, const std::list<T> & a)
{
	s<<a.size();
	typename std::list<T>::const_iterator i;	
	ITERATEX(i,a) s<<*i;

	return s;
}

template <class T> BIStorage & operator >>(BIStorage & s, std::list<T> & a)
{
	a.clear();
	size_t z;
	s>>z;
	T x;
	LOOP(size_t,j,z)
	{
		s >> x;
		a.push_back(x);
	};
	return s;
}



template <class T> BOStorage & operator <<(BOStorage & s, const std::set<T> & a)
{
	s<<a.size();
	typename std::set<T>::const_iterator i;
	ITERATEX(i,a) s<<*i;
	return s;
}

template <class T> BIStorage & operator >>(BIStorage & s, std::set<T> & a)
{
	a.clear();
	size_t z;
	s>>z;
	T x;
	LOOP(size_t,j,z)
	{
		s>>x;
		a.insert(x);
	};
	return s;
}


template <class X, class Y> BOStorage & operator <<(BOStorage & s, const std::map<X,Y> & a)
{
	s<<a.size();
	typename std::map<X,Y>::const_iterator i;
	ITERATEX(i,a) s<<*i;
	return s;
}

template <class X, class Y> BIStorage & operator >>(BIStorage & s, std::map<X,Y> & a)
{
	a.clear();
	size_t z;
	s>>z;
	std::pair<X,Y> t;
	LOOP(size_t,j,z)
	{
		s>>t;
		a.insert(t);
	};
	return s;
}


SGU_NS_END

#endif
